package imooc_math.sort;

import java.util.Arrays;

import resource.SortTestHelper;

public class MergeSortBU {
	public static void merge(Comparable[] arry,int l,int mid,int r){
		//使用克隆数组的原因：避免打乱左右两边已经排好的顺序
		Comparable[] tmp=Arrays.copyOfRange(arry,l,r+1);//[0,r-l]
		int i=l,j=mid+1;//最终要使[i,mid]与[mid+1,r]有序，
		//这里k从l遍历到r，为arry这个数组从l到r重新赋值；赋值的条件是对克隆数组tmp的比较
		for(int k=l;k<=r;k++){//从l-r进行比较
			if(i>mid){
				arry[k]=tmp[j-l];
				j++;
			}else if(j>r){
				arry[k]=tmp[i-l];
				i++;
			}else if(tmp[i-l].compareTo(tmp[j-l])<0){
				arry[k]=tmp[i-l];
				i++;
			}else{
				arry[k]=tmp[j-l];
				j++;
			}
		}
	}
	public static Object[] sort(Comparable[] arry){
		int n=arry.length;
		
		for(int size=1;size<=n;size=size*2){//每次比较的大小
			for(int i=0;i+size<n;i+=2*size){
				merge(arry,i,i+size-1,Math.min(n-1, i+size+size-1));
			}
		}
		return arry;
	}
	public static void main(String[] args) {
		Integer[] arry=SortTestHelper.generateRandomArray(100000, 0, 100000);
		Integer[] arry1=Arrays.copyOf(arry,arry.length);
		Integer[] arry2=Arrays.copyOf(arry,arry.length);
		Integer[] arry3=Arrays.copyOf(arry,arry.length);
		/*Integer[] arry1=(Integer[])sort(arry);
		System.out.println(SortTestHelper.isSorted(arry1));*/
		System.out.println(SortTestHelper.isSorted(arry));
		SortTestHelper.testSort("imooc_math.MergeSort", arry);
		System.out.println(SortTestHelper.isSorted(arry1));
		SortTestHelper.testSort("imooc_math.MergeSortBU", arry1);
		/*System.out.println(SortTestHelper.isSorted(arry2));
		SortTestHelper.testSort("imooc_math.InsertionSort", arry2);*/
		System.out.println(SortTestHelper.isSorted(arry3));
		SortTestHelper.testSort("imooc_math.QuickSort", arry3);
		
	}
}
